Khi được sử dụng với vai trò cấu trúc dữ liệu, đối thủ chính của ma trận kề là danh sách kề. Do mỗi ô trong ma trận kề chỉ đòi hỏi một bit, nên chúng có thể được biểu diễn bằng một cách rất gọn, chỉ chiếm n2/8 byte bộ nhớ liên tục, trong đó n là số đỉnh. Ngoài việc tiết kiệm bộ nhớ, lưu trữ gọn gàng này còn khuyến khích locality of reference (tính địa phương của các truy nhập đến bộ nhớ).

Mặt khác, khi dùng cho đồ thị thưa, danh sách kề lại thắng thế, do chúng không lưu trữ các cạnh không tồn tại. Sử dụng cài đặt danh sách liên kết đơn giản trên một máy tính 32-bit, một danh sách kề cho một đồ thị vô hướng cần khoảng 16e byte, trong đó e là số cạnh của đồ thị.

Lưu ý rằng một đồ thị có thể có nhiều nhất n2 cạnh (kể cả các khuyên). Giả sử d = e/n2 ký hiệu mật độ của đồ thị. Ta có: 16e > n2/8, có nghĩa là danh sách kề chiếm nhiều không gian hơn khi d > 1/128. Do đó, chỉ nên dùng danh sách kề với đồ thị thưa.

Bên cạnh thỏa hiệp về không gian bộ nhớ, các cấu trúc dữ liệu khác nhau còn tạo thuận lợi cho các thao tác dữ liệu khác nhau. Với một danh sách kề, ta dễ dàng tìm mọi đỉnh kề với một đỉnh cho trước; ta chỉ cần đọc danh sách kề của đỉnh đó. Với một ma trận kề, ta phải duyệt toàn bộ một hàng, việc đó cần thời gian O(n). Còn nếu ta lại muốn biết giữa hai đỉnh cho trước có cạnh nối hay không, điều này có thể được xác định ngay lập tức với một ma trận kề, trong khi đó với một danh sách kề, việc này đòi hỏi thời gian tỷ lệ thuận với bậc nhỏ nhất của các đỉnh trong đồ thị.